package com.xj.algorithm.leetcode;

/**
 * 数字的补数
 */
public class L476_二进制的反码 {

    /**
     * 给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。
     * 示例 1:
     *
     * 输入: 5
     * 输出: 2
     * 解释: 5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。
     * 示例 2:
     *
     * 输入: 1
     * 输出: 0
     * 解释: 1 的二进制表示为 1（没有前导零位），其补数为 0。所以你需要输出 0 。
     *  
     *
     * 注意:
     *
     * 给定的整数保证在 32 位带符号整数的范围内。
     * 你可以假定二进制数不包含前导零位。
     * 本题与 1009 https://leetcode-cn.com/problems/complement-of-base-10-integer/ 相同
     */
    public static void main(String[] args) {
        System.out.println(findComplement(5));
        System.out.println(findComplement(1));

        System.out.println(findComplementGood(5));
        System.out.println(findComplementGood(1));
    }

    //自己的解法：位运算，异或。构造全为1的数，移动然后-1
    public static int findComplement(int num) {
        //~num  波浪线是取反操作，不过最高位也被取反了。不符合题意

        int tmp = num;

        //构造和num位数一样的全为1的数
        int num2 = 1;
        while(tmp > 0){
            num2 <<= 1; //左移动，新增的数是0
            tmp >>= 1;
        }
        num2 -= 1;
        return num^num2;
    }

    //精彩解法：模拟位运算的操作，逐个比较
    public static int findComplementGood(int num) {
        int result = 0;
        int temp = 1;

        while (num > 0) {
            //遇到为0的位 我们就要置1
            if ((num & 1) == 0) {
                result = result | temp;
            }
            // 让temp去移动可能要变更的位
            temp <<= 1;
            num >>= 1;
        }
        return result;
    }

}
